class Solution {
    //贪心算法:当n>=5时，我们应尽可能把绳子剪成长度为3或2的绳子
    //n的数字过大，动态规划已时间复杂度过大
    //大数求余越界问题：循环求余法、快速幂求余（二分求余）
public:
    int cuttingRope(int n) {
        if(n < 2)  return -1;
        if(2 == n)  return 1;
        if(3 == n)  return 2;

        int timesOf3 = n / 3;  //长为3的绳子段数
        int timesOf2 = 0;
        
        if((n - timesOf3*3) == 1){
            timesOf2 = 2;
            --timesOf3;
        }else if((n - timesOf3*3) == 2){
            timesOf2 = 1;
        }else{}

        //循环取余
        // long result3 = 1;
        // for(int i = 0; i < timesOf3; ++i){
        //     result3 *= 3;
        //     result3 %= 1000000007;
        // }

        //快速幂
        long long result3 = 1;
        int mod = 1000000007;
        long long rem = 3;
        while(timesOf3 > 0){
            if(timesOf3 % 2) result3 = (result3 * rem) % mod;
            rem = (rem * rem) % mod;
            timesOf3 /= 2;
        }

        int result2 = (int)(pow(2, timesOf2));

        long long result = (result2 * (result3)) % mod;
        return (int)result;
    }
};